package com.shm.leetcode;

import java.util.Arrays;

/**
 * @author: shm
 * @dateTime: 2020/12/3 9:43
 * @description: 204. 计数质数
 * 统计所有小于非负整数 n 的质数的数量。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 10
 * 输出：4
 * 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 * 示例 2：
 *
 * 输入：n = 0
 * 输出：0
 * 示例 3：
 *
 * 输入：n = 1
 * 输出：0
 *
 *
 * 提示：
 *
 * 0 <= n <= 5 * 106
 */
public class CountPrimes {
    /**
     * 方法一：枚举
     * 很直观的思路是我们枚举每个数判断其是不是质数。
     *
     * 考虑质数的定义：在大于 11 的自然数中，除了 11 和它本身以外不再有其他因数的自然数。因此对于每个数 xx，我们可以从小到大枚举 [2,x-1][2,x−1] 中的每个数 yy，判断 yy 是否为 xx 的因数。但这样判断一个数是否为质数的时间复杂度最差情况下会到 O(n)O(n)，无法通过所有测试数据。
     *
     * 考虑到如果 yy 是 xx 的因数，那么 \frac{x}{y}
     * y
     * x
     * ​
     *   也必然是 xx 的因数，因此我们只要校验 yy 或者 \frac{x}{y}
     * y
     * x
     * ​
     *   即可。而如果我们每次选择校验两者中的较小数，则不难发现较小数一定落在 [2,\sqrt{x}][2,
     * x
     * ​
     *  ] 的区间中，因此我们只需要枚举 [2,\sqrt{x}][2,
     * x
     * ​
     *  ] 中的所有数即可，这样单次检查的时间复杂度从 O(n)O(n) 降低至了 O(\sqrt{n})O(
     * n
     * ​
     *  )。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n\sqrt{n})O(n
     * n
     * ​
     *  )。单个数检查的时间复杂度为 O(\sqrt{n})O(
     * n
     * ​
     *  )，一共要检查 O(n)O(n) 个数，因此总时间复杂度为 O(n\sqrt{n})O(n
     * n
     * ​
     *  )。
     *
     * 空间复杂度：O(1)O(1)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-by-leetcode-solution/
     * @param n
     * @return
     */
    public int countPrimes(int n) {
        int ans = 0;
        for(int i=2;i<n;i++){
            ans+=isPrime(i)?1:0;
        }
        return ans;
    }

    public boolean isPrime(int n){
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }

    /**
     * 方法二：埃氏筛
     * 枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法，该算法由希腊数学家厄拉多塞（\rm EratosthenesEratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。
     *
     * 我们考虑这样一个事实：如果 xx 是质数，那么大于 xx 的 xx 的倍数 2x,3x,\ldots2x,3x,… 一定不是质数，因此我们可以从这里入手。
     *
     * 我们设 \textit{isPrime}[i]isPrime[i] 表示数 ii 是不是质数，如果是质数则为 11，否则为 00。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 00，这样在运行结束的时候我们即能知道质数的个数。
     *
     * 这种方法的正确性是比较显然的：这种方法显然不会将质数标记成合数；另一方面，当从小到大遍历到数 xx 时，倘若它是合数，则它一定是某个小于 xx 的质数 yy 的整数倍，故根据此方法的步骤，我们在遍历到 yy 时，就一定会在此时将 xx 标记为 \textit{isPrime}[x]=0isPrime[x]=0。因此，这种方法也不会将合数标记为质数。
     *
     * 当然这里还可以继续优化，对于一个质数 xx，如果按上文说的我们从 2x2x 开始标记其实是冗余的，应该直接从 x\cdot xx⋅x 开始标记，因为 2x,3x,\ldots2x,3x,… 这些数一定在 xx 之前就被其他数的倍数标记过了，例如 22 的所有倍数，33 的所有倍数等。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n\log \log n)O(nloglogn)。具体证明这里不再展开，读者可以自行思考或者上网搜索，本质上是要求解 \sum_{p}\frac{n}{p}∑
     * p
     * ​
     *
     * p
     * n
     * ​
     *   的和，其中 pp 为质数。当然我们可以了解这个算法一个比较松的上界 O(n\log n)O(nlogn) 怎么计算，这个等价于考虑 \sum_{i=1}^{n}\frac{n}{i}∑
     * i=1
     * n
     * ​
     *
     * i
     * n
     * ​
     *   的和，而 O(\sum_{i=1}^{n}\frac{n}{i}) = O(n\sum_{i=1}^{n}\frac{1}{i})O(∑
     * i=1
     * n
     * ​
     *
     * i
     * n
     * ​
     *  )=O(n∑
     * i=1
     * n
     * ​
     *
     * i
     * 1
     * ​
     *  )，而 11 到 nn 中所有数的倒数和趋近于 \log nlogn，因此 O(n\sum_{i=1}^{n}\frac{1}{i})=O(n\log n)O(n∑
     * i=1
     * n
     * ​
     *
     * i
     * 1
     * ​
     *  )=O(nlogn)。
     * 空间复杂度：O(n)O(n)。我们需要 O(n)O(n) 的空间记录每个数是否为质数。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-by-leetcode-solution/
     * @param n
     * @return
     */
    public int countPrimes_2(int n) {
        int[] isPrime = new int[n];
        Arrays.fill(isPrime,1);
        int ans = 0;
        for (int i=2;i<n;i++){
            if (isPrime[i]==1){
                ans++;
                if ((long)i*i<n){
                    for(int j=i*i;j<n;j+=i){
                        isPrime[j]=0;
                    }
                }
            }
        }
        return ans;
    }


}
